%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                               %
% This doc is a member of Oneplus' NOTE LAB     %
%                                               %
% There are many bugs and incompletion.         %
% Wish this will help you.                      %
% If any update you can make, please conect     %
%                                               %
% Oneplus <oneplus.lau@gmail.com>               %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{ctexart}
\usepackage[top = 1.25in, bottom=1in, left=1in, right=1in]{geometry}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{listings}
\usepackage{ifthen}
\usepackage{color}
\usepackage{latexsym}

\definecolor{grey}{rgb}{0.3,0.3,0.3}
\definecolor{darkgreen}{rgb}{0,0.3,0}
\definecolor{darkblue}{rgb}{0,0,0.3}
\definecolor{lightgrey}{rgb}{0.9,0.9,0.9}
\definecolor{darkgrey}{rgb}{0.1,0.1,0.1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Note For Compiling Teconology                  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{fancyhdr}
\fancyhead[C]{《编译原理笔记》~~~~~~~~~学号：1080310226~~~~~~~~~姓名：刘一佳}
\fancyhead[L]{}\fancyhead[R]{}
\makeatletter
\def\headrule{{\if@fancyplain\let\headrulewidth\plainheadrulewidth\fi%
 \hrule\@height 1.0pt \@width\headwidth\vskip1pt%
 \hrule\@height 0.5pt\@width\headwidth%
 \vskip-2\headrulewidth\vskip-1pt}}
\makeatother
\pagestyle{fancy}

\begin{document}
    \section{高级语言及其文法}
        \subsection{基本定义}
            \begin{itemize}
                \item \textbf{字符、字母} 基本元素
                \item \textbf{字母表} 集合，\textbf{非空}集合，非空\textbf{有穷}集合，\textbf{字母}或\textbf{字符}的集合
                \item \textbf{字母表的运算}
                    \begin{itemize}
                        \item 乘积
                        \item 幂
                        \item 正闭包、克林闭包
                    \end{itemize}
                \item \textbf{句子}
                \item 前缀、后缀、真前缀、真后缀
                \item \textbf{公共子串}、\textbf{最大公共子串}
                \item \textbf{语言}
            \end{itemize}
        \subsection{文法的定义}
            \begin{itemize}
                \item \textbf{文法} $G=(V,T,S,P)$
                \item \textbf{推导}、\textbf{派生}
            \end{itemize}
        \subsection{文法的分类}
            \begin{itemize}
                \item 0型文法、1型文法$|\beta|\ge|\alpha|$、2型文法，在1型文法的基础上，$\alpha \in V$是CFG
            \end{itemize}
        \subsection{CFG的文法树}
            \begin{itemize}
                \item 语法树
                \item 结果
                \item 子树
                \item 短语，直接短语
                    \begin{itemize}
                        \item 句型本身是短语
                        \item 句型的任何一个级数至少为2的A子树是\textbf{短语}
                        \item 句型的任何一个级数为2的A子树是\textbf{直接短语}
                    \end{itemize}
                \item \textbf{句柄} 最左直接短语
                \item \textbf{最左推导} 每一步都是对于当前\textbf{句型}的\textbf{最左变量(最左非终结符)}进行替换。
            \end{itemize}
        \subsection{CFG的二义性}
    \section{词法分析}
        \subsection{词法分析器的功能}
            \subsubsection{词法分析器的作用}
                词法分析器是将\textbf{构成源程序的字符串}转化成等价的\textbf{单词(记号)序列}
            \subsubsection{词法分析阶段的错误处理}
                \begin{itemize}
                    \item 非法字符检查
                    \item 关键字拼写错误检查
                    \item 不封闭错误检查
                    \item 重复说明检查
                    \item 错误恢复与续编译
                \end{itemize}
    \section{自顶向下的语法分析}
        \subsection{语法分析概述}
            语法分析的作用是检查词法分析产生的单词序列是否构成源语言中的句子。
        \subsection{自顶向下的语法分析面临的问题与文法的改造}
            \subsubsection{自顶向下分析面临的问题}
                \begin{itemize}
                    \item 二义性问题
                    \item 回溯问题
                    \item 左递归\textbf{引起无穷推导}
                        \begin{itemize}
                            \item \textbf{递归} $A\Rightarrow\alpha A\beta$，则称文法G是递归的。
                            \item \textbf{左递归} 递归，且$\alpha = \varepsilon$
                            \item \textbf{间接递归} 递归，$A\Rightarrow\alpha A\beta$需要经过两步推导
                            \item \textbf{直接递归} 递归，存在$A\rightarrow\alpha A\beta$这样的产生式
                        \end{itemize}
                \end{itemize}
            \subsubsection{对于上下文无关文法的改造}
                \begin{itemize}
                    \item 消除二义性
                    \item 消除左递归 将$A\rightarrow A\alpha|\beta$替换为\[A\rightarrow \beta A'\]\[ A'\rightarrow \alpha A' | \varepsilon \]\\
                        消除左递归算法
                        \begin{enumerate}
                            \item 枚举非终结符i
                            \item ~~~~枚举非终结符j
                            \item ~~~~~~~~用对于所有Aj的产生式当前的产生式替换$Ai\rightarrow Aj\beta$的产生式
                            \item ~~~~消除Ai的左递归
                        \end{enumerate}
                    \item 提取因子 对于形如$A\rightarrow \alpha \beta_1 | \beta_2$的产生式，用\[A\rightarrow \alpha A'\]\[A'\rightarrow \beta_1 | \beta_2\]替换
                \end{itemize}
                将一个文法变成LL(1)文法的方法就是进行上面三步操作。
            \subsubsection{LL(1)文法}
                FIRST集
                \begin{itemize}
                    \item \textbf{FIRST集} $FIRST(\alpha)=\{a|\alpha \Rightarrow a\beta, a \in T, \beta \in (V \cup T)*\}$
                    \item \textbf{FIRST集理解} 输入是句子、集合、终结符集合、从某一句子，可以推导出的最左的终结符
                    \item \textbf{特殊情况} 如果从某一句子a可以推出$\varepsilon$，那么$\varepsilon \in FIRST(a)$
                \end{itemize}

                FOLLOW集
                \begin{itemize}
                    \item \textbf{FOLLOW集} $FOLLOW(A)=\{a|S\Rightarrow\alpha Aa \beta, a\in T, \alpha,\beta in(V\cup T)*\}$
                    \item \textbf{FOLLOW集的理解} 输入是非终结符、集合、终结符集合、某一非终结符紧随的最左终结符
                    \item \textbf{特殊情况} 如果A是某个句型的最右符号，那么'\#'填入FOLLOW(A)
                \end{itemize}

                LL(1)文法，对于有相同左部的产生式$A\rightarrow \alpha|\beta$满足下列条件：
                \begin{enumerate}
                    \item 若$\alpha$,$\beta$都不能推出$\varepsilon$，那么$FIRST(\alpha) \cap FIRST(\beta) = \emptyset $
                    \item $\alpha,\beta$至多有一个可以推出$\varepsilon$
                    \item 若$\beta\Rightarrow \varepsilon$，则$FIRST(\alpha) \cap FOLLOW(A) = \emptyset$
                \end{enumerate}
        \subsection{预测分析法}
            \subsubsection{预测分析器的构成}
                预测分析算法
                \begin{enumerate}
                    \item 初始化将"\#"和开始符号S压入栈中
                    \item 重复下面过程指导栈为空
                    \item ~~~~X为当前栈顶，a为输入符号
                    \item ~~~~~~~~如果当前栈顶是终结符或'\#'
                    \item ~~~~~~~~~~~~如果X=a就弹栈
                    \item ~~~~~~~~如果是非终结符
                    \item ~~~~~~~~~~~~看表中M[X,a]项
                    \item ~~~~~~~~~~~~将X弹出，并将M[X,a]的产生式倒序压入栈中
                    \item ~~~~~~~~~~~~输出产生式
                \end{enumerate}
            \subsubsection{预测分析表的构造}
                \begin{enumerate}
                    \item 枚举G中的产生式$A\rightarrow \alpha$
                    \item ~~~~枚举$FIRST(\alpha)$中的所有终结符，将$A\rightarrow \alpha$填入M[A,a]
                    \item ~~~~若$\varepsilon \in FIRST(\alpha)$
                    \item ~~~~~~~~~枚举所有$FOLLOW(A)$中的终结符a，将$A\rightarrow \alpha$填入M[A,a]
                    \item ~~~~若$\varepsilon \in FIRST(\alpha)$且$\#\in FOLLOW(A)$
                    \item ~~~~~~~~~将$A\rightarrow \alpha$填入M[A,\#]
                \end{enumerate}
            \subsubsection{预测分析中的错误处理}
        \subsection{递归下降分析法}
            \subsubsection{递归下降分析法的基本思想}
                所谓递归下降分析法，是指根据各个候选式的结构，为文法的每个语法变量编写一个处理子程序，用来识别该语法变量所代表的语法成分。
            \subsubsection{语法图和递归子程序}
            \subsubsection{基于语法图的语法分析器的工作方式}
            \subsubsection{语法图的化简与实现}
                用循环代替尾递归
            \subsubsection{递归子程序的实现步骤}
                \begin{enumerate}
                    \item 构造文法G
                    \item 改造文法
                    \item 求FIRST集合FOLLOW集
                    \item 构造LL(1)分析表
                    \item 绘制语法图
                    \item 化简语法图
                    \item 编制子程序
                \end{enumerate}
    \section{自底向上的语法分析}
        \subsection{自底向上的语法分析概述}
            \subsubsection{移进-归约分析}
            \subsubsection{优先法}
                \begin{itemize}
                    \item 句柄内各符号同时归约，因此规定句柄各相邻符号优先级相同
                    \item 因为句柄要归约，所以规定句柄两端的优先级要高于句柄外与之相邻的符号的优先级
                \end{itemize}
            \subsubsection{状态法}
                \begin{itemize}
                    \item 用状态描述不同时刻形成的那部分句柄
                    \item 因为句柄是产生式的右部，所以可用产生式来表示句柄的不同状态
                \end{itemize}
        \subsection{算符优先分析法}
            \subsubsection{算符优先文法}
                判断依据是文法中不存在“归约-归约冲突”(项目集合中同时含有形如$A\rightarrow \alpha.$和$B\rightarrow \beta.$)和“移进-归约冲突”(项目集合中同时含有形如$A\rightarrow \alpha.a\beta$和$B\rightarrow \gamma.$的项目 )
            \subsubsection{算符优先矩阵的构造}
                \begin{itemize}
                    \item \textbf{FIRSTOP集} 从非终结符V可以最早推导出的终结符 $FIRSTOP(B)=\{b|B\Rightarrow b...或B\Rightarrow Ab...\}$
                    \item \textbf{LASTOP集} 从非终结符V可以推出的最晚的终结符 $LASTOP(B)=\{a|B\Rightarrow ...a或B\Rightarrow ...aC,a \in T, C \in V\}$
                \end{itemize}
                算符优先矩阵的构造
                \begin{itemize}
                    \item 枚举所有产生式，关注的内容是产生式右部。
                    \item ~~~~对于$A\rightarrow ...aB...$的产生式$a<FIRSTOP(T)$
                    \item ~~~~对于$A\rightarrow ...Bb...$的产生式$LASTOP(T)>b$
                \end{itemize}
            \subsubsection{算符优先分析算法}
                \begin{itemize}
                    \item 初始化，将'\#'放入栈顶
                    \item 从输入读入一个符号R
                    \item 如果栈顶符号的优先级\textbf{高于}读入符号
                    \item ~~~~比较栈中两个相邻的两个符号
                    \item ~~~~~~~~直到前者优先级大于等于后者
                    \item ~~~~弹栈，进行归约，并将归约结果放到栈顶
                \end{itemize}
            \subsubsection{优先函数}
        \subsection{LR分析法}
            \subsubsection{LR分析算法}
            \subsubsection{LR(0)分析表的构造}
                定义
                \begin{itemize}
                    \item \textbf{LR(0)项目}
                    \item \textbf{拓广文法}
                    \item \textbf{闭包}
                    \item \textbf{GO函数}
                    \item \textbf{LR(0)项目集规范族}
                \end{itemize}

                LR(0)分析法构造算法
                \begin{itemize}
                    \item 构造LR(0)项目集规范族，每个族作为一个状态
                    \item 枚举所有状态
                    \item ~~~~找点的位置
                    \item ~~~~~~~~如果点不在结尾（移近项目）
                    \item ~~~~~~~~~~~~如果紧随点的是终结符，那么action[A,a]=GO(A,a)
                    \item ~~~~~~~~~~~~如果紧随点的是非终结符，那么GOTO[A,B]=GO(A,B)
                    \item ~~~~~~~~如果点在结尾（归约项目）
                    \item ~~~~~~~~~~~~那么，枚举所有终结符和'\#'，令action[A,a]=rj
                \end{itemize}

                SLR(1)分析表的构造算法\\
                如果点在结尾，那么枚举所有FOLLOW(A)集中的终结符a，令action[A,a]=rj

                LR(1)文法的闭包算法
                \begin{itemize}
                    \item 枚举项目集中所有的项目[$A\rightarrow\alpha.B\beta,a$]
                    \item ~~~~枚举所有$B\rightarrow \eta$的产生式
                    \item ~~~~~~~~枚举所有$b \in FIRST(\beta a)$
                    \item ~~~~~~~~~~~~把所有[$B\rightarrow .\eta,b$]放到集合中
                \end{itemize}

                LR(1)分析表的构造算法
                \begin{itemize}
                    \item 构造项目集规范族
                    \item 枚举每个项目集
                    \item ~~~~枚举项目集中的每个项目
                    \item ~~~~~~~~如果点不在结尾（移近项目）
                    \item ~~~~~~~~~~~~如果紧随点的是终结符，那么action[A,a]=GO(A,a)
                    \item ~~~~~~~~~~~~如果紧随点的是非终结符，那么GOTO[A,B]=GO(A,B)
                    \item ~~~~~~~~如果点在结尾（归约项目[$A\rightarrow p,a$]）
                    \item ~~~~~~~~~~~~那么，只令action[A,a]=rj
                \end{itemize}
    \section{语法制导翻译与属性文法}
        \subsection{语法制导翻译概述}
            \textbf{前端与后端}
            \begin{itemize}
                \item 前端，词法分析、语法分析、语义分析、中间代码生成、符号表建立
                \item 后端，代码优化、目标代码生成、符号表访问、相关错误处理
            \end{itemize}

            \textbf{语法制导定义}\\
            将静态检查与中间代码生成结合到语法分析中进行的技术称为语法制导翻译

            \textbf{}\\

    \section{运行时的存储组织}
        \subsection{与存储组织有关的源语言概念与特征}
            \subsubsection{名字及其绑定}
                \begin{itemize}
                    \item 限定名
                    \item 环境
                    \item 状态
                \end{itemize}
            \subsubsection{声明的作用域}
                \begin{itemize}
                    \item 静态作用域
                    \item 显示访问控制
                    \item 动态作用域
                \end{itemize}
            \subsubsection{过程及其活动}
                \begin{itemize}
                    \item 过程定义、过程名、过程体
                    \item 形式参数、实在参数
                    \item 活动、生存期
                \end{itemize}
            \subsubsection{参数传递方式}
                \begin{enumerate}
                    \item 传值
                    \item 传地址
                    \item 传值结果
                    \item 传名
                \end{enumerate}
        \subsection{存储组织}
            \subsubsection{运行时内存的划分}
            \subsubsection{活动记录}
            \subsubsection{局部数据的组织}
            \subsubsection{全局存储分配策略}
        \subsection{}
    \section{习题简答题}
        \begin{enumerate}
            \item 简要说明机器语言、汇编语言、高级语言的特点\\
                \textbf{机器语言、汇编语言} 0、1代码与助记符：更接近于计算机硬件指令系统的工作\\
                \textbf{高级语言} 其表示方法更接近于待解问题的表示方法
            \item 翻译程序有哪几种？他们的功能是什么\\
                参考PPT chapter1-11
            \item 汇编语言程序和汇编程序是什么关系\\
            \item 什么是编译程序？什么是编译系统\\
                \textbf{编译程序} 将源程序完整地转换成机器语言程序或汇编语言程序，然后再处理、执行的翻译程序\\
                \textbf{编译系统} 编译系统=编译程序+运行系统
            \item 给出编译程序和解释程序的异同\\
                \textbf{相同点} 都是翻译程序，都能实现源代码到机器语言或汇编语言的转换\\
                \textbf{不同点}\\
                    \textbf{编译程序} 将源程序完整地转换成机器语言程序或汇编语言程序，然后再处理、执行的翻译程序\\
                    \textbf{解释程序} 一边解释一边执行的翻译程序
            \item 编译程序的总体结构图\\
                \begin{figure}[hbtp]
                    \includegraphics[width=200px]{images/chap1.jpg}\\
                \end{figure}
            \item 试述词法分析器的功能\\
                词法分析器读入表示源程序的字符流，按照程序功能等价的要求，将其转换成对应的单词序列，并剔除其中的空格、注释等不影响程序语义的字符。
            \item 语法分析程序的主要任务是什么\\
                语法分析程序的任务是检查词法分析器输出的单词序列是否构成源语言中的句子。
            \item 在自顶向下分析法中为什么不允许文法中出现左递归\\
                左递归会造成无穷推导
        \end{enumerate}
\end{document}
